package leetcode.editor.cn.dsa18_searchtree;
// 给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

public class MaximumSumBstInBinaryTree1373_1 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        class Result {
            int min;
            int max;
            int sum;
            boolean isBST;
            public Result(int min, int max, int sum, boolean isBST) {
                this.min = min;
                this.max = max;
                this.sum = sum;
                this.isBST = isBST;
            }
        }
        public int maxSumBST(TreeNode root) {
            int[] max = new int[1];
            traverse(root, max);
            return max[0];
        }
        // 优化解法：使用后序遍历方式
        private Result traverse(TreeNode root, int[] max) {
            if (root == null) return null; // 递归终止条件
            Result leftResult = traverse(root.left, max); // 遍历左子树
            Result rightResult = traverse(root.right, max); //遍历右子树
            // 判断是否满足BST条件
            if (leftResult != null && (!leftResult.isBST || leftResult.max >= root.val)) {
                return new Result(Integer.MIN_VALUE,Integer.MAX_VALUE,0,false);
            }
            if (rightResult != null && (!rightResult.isBST || rightResult.min <= root.val)) {
                return new Result(Integer.MIN_VALUE,Integer.MAX_VALUE,0,false);
            }
            int minVal = root.val;
            int maxVal = root.val;
            int sum = root.val;
            if (leftResult != null) {
                minVal = leftResult.min;
                sum += leftResult.sum;
            }
            if (rightResult != null) {
                maxVal = rightResult.max;
                sum += rightResult.sum;
            }
            // 保存最大值
            max[0] = Math.max(max[0], sum);
            return new Result(minVal, maxVal, sum,true);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}